package com.justnow;

import java.util.HashMap;
import java.util.Map;

public class TwoNumberSum {

    /**
     * 方法一:0(n^2)
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        int[] retValue = null;
        int length = nums.length;
        for (int i = 0; i < length; i++) {

/**
 *

            for (int j = 0; j < length; j++) {
                if ((nums[i] + nums[j] == target) && (i != j)) {
                    retValue[0] = i;
                    retValue[1] = j;
                    break;
                }
            }
*/

            //让j=i+1，可以避免重复的计算过程
            //retValue 直接将其初始化为retValue的内容

            for (int j = i + 1; j < length; j++) {
                if (nums[i] + nums[j] == target) {
                    retValue = new int[]{i, j};
                }
            }
        }
        return retValue;
    }

    /**
     * 方法二：0(n)，将数组中的数据保存到map中，然后根据map中查找target与遍历的结果之间的差值,在map中查找差值！
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum2(int[] nums, int target) {
        int[] retValue = null;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                retValue = new int[]{i, map.get(complement)};
                break;
            }
        }

        return retValue;
    }

    /**
     * 方法三，一边往哈希表中传入数据，一边计算是否存在复合要求的数
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum3(int[] nums, int target) {
        int[] retValue = null;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement))
                retValue = new int[] {map.get(complement), i};
            map.put(nums[i], i);
        }
        return retValue;
    }


}
